In many digital systems, a plurality of devices share a common resource. For example, in most digital computers, devices such as processors and memories share a common bus over which addresses, instructions, and data are transferred. In the systems, it is apparent that if the resource such as a bus cannot be shared simultaneously, there must be a means to determine what device will have access to the resource when it becomes available.
In some systems, where processing and input/output are provided by a single processor, there may be no arbitration for a common bus because the processor always determines the sequence of bus activity. For example, the processor may put an address for an instruction on the bus and then wait for the memory to respond. However, when there are a plurality of processors such as in a distributed processing system or when there is direct memory access, a method may be required to arbitrate what device will gain access to the bus when the present cycle is finished. There have been a number of prior art solutions to the common resource arbitration problem, each solution typically having advantages and disadvantages.
One prior art method of providing bus arbitration is to use a centralized priority encoder which receives an input from each device that requests the bus. Generally, the encoder has a plurality of lines for output over which it transmits a priority code indicative of which device requesting the bus has the highest priority. A significant disadvantage of this type of system is that a single point failure in the encoder will cause the entire system to become unavailable. Accordingly, this method is not preferable for a fault-tolerant system. Furthermore, the approach generally requires at least one line connected between each device and the encoder in addition to the priority code lines.
A second prior art approach to bus arbitration is commonly referred to as "daisy chaining." In this method, a bus available signal is passed from device to device in a priority order. A device desiring access to the bus captures the signal and gets access to the bus. In addition to the disadvantage of becoming unavailable by a single-point failure, a system utilizing this approach also provides relatively slow arbitration and often has the priority of devices determined by the physical positioning of device boards. Furthermore, if a device board is removed from the original system configuration, rewiring is generally required so that the bus available signal may be transferred past the open slot.
A third prior art method uses a set of lines whereby a lower priority device is blocked by a higher priority device requesting access to the bus. This approach to bus arbitration has the disadvantage of requiring a relatively large number of interconnect block lines between devices. As the lines are generally connected in open collector logic, a considerable amount of power is consumed by the system in maintaining the blocking signal.
A bus arbitration apparatus was required for a distributed processing fault tolerant space system wherein arbitration was to be accomplished in a relatively short time period, with a minimum number of interconnect lines, and with a minimum amount of power. All of the prior art bus arbitration approaches had significant drawbacks.